package org.leetcode.middle.leetcode98;

import org.leetcode.TreeNode;

public class Solution {

    public boolean isValidBST3(TreeNode root) {

        return DFS(root,Long.MIN_VALUE,Long.MAX_VALUE);
    }

    private boolean DFS(TreeNode root,long left,long right){
        if (root==null){
            return true;
        }

        if (root.val>=left && root.val<=right){
            boolean leftIsValid = DFS(root.left, left, root.val);
            boolean rightIsValid = DFS(root.right, root.val, right);

            return leftIsValid && rightIsValid;
        }

        return false;
    }

    public boolean isValidBST2(TreeNode root) {
        return TopDownDFS(root,Long.MIN_VALUE,Long.MAX_VALUE);
    }

    private boolean TopDownDFS(TreeNode root, long low, long high) {
        if (root == null) {
            return true;
        }
        if (root.val >= low && root.val <= high) {
            boolean left = TopDownDFS(root.left, low, root.val);
            boolean right = TopDownDFS(root.right, root.val, high);

            return left && right;
        } else return false;

    }


    TreeNode max;

    public boolean isValidBST(TreeNode root) {

        if (root == null) {
            return true;
        }

        boolean left = isValidBST(root.left);

        if (!left) {
            return false;
        }

        if (max != null && root.val <= max.val) {
            return false;
        }

        max = root;

        boolean right = isValidBST(root.right);

        return right;

    }
}
